In recent years, a cryptosystem based on pairing on the elliptic curve has been brought to attention (e.g., Nonpatent Reference 3). According to this cryptosystem, a user's public key can be generated based on ID (Identifier) information etc., and thereby it is not necessary to guarantee the validity of the public key.
Meanwhile, when performing a pairing computation on an elliptic curve by using a processing device, such as a computer, it is a problem how to quickly perform the pairing computation in a large amount of computation by using a processing device with low computational capacity. As a method for solving this problem, Nonpatent References 1 and 2 are proposed.
The security of these encryption technologies is based on that it takes enormous time for the computational capacity of existing processing devices, such as a computer, to break the encryption.
[Nonpatent Reference 1]: M. Scott, “Faster pairings using an elliptic curve endomorphism”, to appear in Indocrypt 2005, Springer Verlag (2005)
[Nonpatent Reference 2]: M. Scott, “Scaling security in pairing-based protocols”, available at http://eprint.iacr.org, 2005
[Nonpatent Reference 3]: Sakai, Ohgishi, and Kasahara, “Cryptosystems based on pairing over the elliptic curve”, The 2001 Symposium on cryptography and information security (SCIS 2001)